package com.learn.finished;
/*
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 */
//二分法---牛顿迭代
public class num_69 {
//    public static int mySqrt(int x) {
//        int index=-1;
//        int left=0,right=x;
//        while (left <= right) {
//            int mid=left+(right-left)/2;//正确
//            int mid1=(left+right)/2;//同样正确，但是运行时间会超出很多,为什么?
//            //此处需要考虑溢出问题，如果输入一个接近整型最大值的数值，即使是一半，平方后也有可能超出int类型，产生溢出
//            //一旦溢出，程序就有可能返回错误的结果
//            if ((long)mid * mid <= x) {
//                index=mid;
//                left=mid+1;
//            }else {
//                right=mid-1;
//            }
//
//        }
//        return index;
//    }

    //牛顿迭代
    public static int mySqrt(int x){
        if (x == 0) {
            return 0;
        }
        return (int) sqrt(x,x);
    }

    public static double sqrt(double i,int x){
        double res=(i+x/i)/2;
        if (res == i) {
            return i;
        }else {
            return sqrt(res,x);
        }
    }
    public static void main(String[] args) {
        //int最大值------------------2147483647
        System.out.println(mySqrt(2147395599));
        System.out.println(mySqrt(24));
    }
}
